Programmable integrated circuits (ICs) are often used to implement digital logic operations according to user configurable input. Example programmable ICs include Complex Programmable Logic Devices (CPLDs) and field programmable gate arrays (FPGAs). CPLDs often include several function blocks that are based on programmable logic array (PLA) architecture with sum-of-products logic. A configurable interconnect matrix transmits signals between the function blocks.
An example FPGA includes an array of configurable logic blocks (CLBs) and a ring or columns of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure (routing resources). The CLBs, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that determine how the CLBs, IOBs, and interconnect structure function. The configuration bitstream may be read from an external memory, conventionally an external integrated circuit memory EEPROM, EPROM, PROM, and the like, though other types of memory may be used. The collective states of the individual memory cells determine the function of the FPGA. A specific type of FPGA uses a look-up-table (LUT)-based CLB. The configuration memory provides input values to a number of multiplexers that are controlled by inputs to the CLB.
A conventional design process for an integrated circuit, such as an ASIC or an FPGA implementation begins with the creation of the design. The design specifies the function of a circuit at a schematic or logic level and may be represented using various hardware description languages (e.g., VHDL, ABEL, or Verilog) or schematic capture programs. The design is synthesized to produce a logical network list (“netlist”), and the synthesized design is mapped onto primitive components within the target device (e.g., programmable logic blocks of an FPGA).
Following mapping, placement of the components of the synthesized and mapped design is then performed for the target device. During placement, each mapped component of the design is assigned to a physical position on the chip. The placer attempts to place connected design objects in close physical proximity to one another in order to conserve space and increase the probability that the desired interconnections between components will be successfully completed by the router. Placing connected components close to one another also generally improves the performance of the circuit, since long interconnect paths are associated with excess capacitance and resistance, resulting in longer delays and greater power consumption.
Specified connections between components of the design are routed within the target device for the placed components. The routing process specifies physical wiring resources that will be used to conduct signals between pins of placed components of the design. For each connection specified in the design, the routing process allocates wire resources necessary to complete the connection. As used herein, the selection and assignment of wire resources in connecting the output pin of one component to the input pin of another component is referred to as routing a net. When nets have been routed using most or all of the wiring resources in a given area, the area is generally referred to as congested, which creates competition for the remaining wiring resources in the area or makes routing of additional nets in the area impossible.
The disclosed embodiments may address one or more of the above issues.